package com.sx.sx1.lintcode.day717;

import java.util.ArrayList;
import java.util.List;

public class LC185 {

    static class Solution {
        /**
         * @param matrix: An array of integers
         * @return: An array of integers
         */
        public int[] printZMatrix(int[][] matrix) {
            int n = matrix.length;
            int m = matrix[0].length;

            int all = n * m;
            int[] ans = new int[all];
            int idx = 0;

            boolean up = false; //false:上到下  true： 下到上

            //先处理m列
            for (int i = 0; i < m; i++) {
                int x = 0, y = i;  //右上角位置
                List<Integer> ll = new ArrayList<>();

                while (x >= 0 && x < n && y >= 0 && y < m) {
                    //ans[idx++] = matrix[x][y];
                    ll.add(matrix[x][y]);
                    //System.out.print(x + "," + y + " => " + matrix[x][y] + " ");
                    x++;
                    y -= 1;
                }

                if (up) {
                    for (int k : ll) {
                        ans[idx++] = k;
                    }
                } else {
                    for (int k = ll.size() - 1; k >= 0; k--) {
                        ans[idx++] = ll.get(k);
                    }
                }
                up = !up;
            }

            //System.out.println();

            //再处理行
            for (int i = 1; i < n; i++) {
                int x = i, y = m - 1; //右上角位置
                List<Integer> ll = new ArrayList<>();
                while (x >= 0 && x < n && y >= 0 && y < m) {
                    //ans[idx++] = matrix[x][y];
                    ll.add(matrix[x][y]);
                    //System.out.print(x + "," + y + " => " + matrix[x][y] + " ");
                    x++;
                    y -= 1;
                }
                if (up) {
                    for (int k : ll) {
                        ans[idx++] = k;
                    }
                } else {
                    for (int k = ll.size() - 1; k >= 0; k--) {
                        ans[idx++] = ll.get(k);
                    }
                }
                up = !up;
            }


            return ans;
        }
    }

    public static void main(String[] args) {
        int[][] arr = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12}
        };

        int[][] arr1 = {
                {1,2},
                {1,2}

        };
        int[] data = new Solution().printZMatrix(arr1);
        for (int i : data) {
            System.out.print(i+" ");
        }
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有199条未读消息，请及时查看
185 · 矩阵的之字型遍历
算法
简单
通过率
27%

题目
题解19
笔记
讨论99+
排名
记录
描述
给你一个包含 m x n 个元素的矩阵 (m 行, n 列), 求该矩阵的之字型遍历。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:
	输入: [[1]]
	输出:  [1]

样例 2:
	输入:
	[
    [1, 2,  3,  4],
    [5, 6,  7,  8],
    [9,10, 11, 12]
  ]

	输出:  [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]

标签
相关题目

161
旋转图像
中等

374
螺旋矩阵
中等

770
最大数和最小数
简单
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
已开启智能提示
发起考试
15 分 00 秒
123456789

控制台
        历史提交

 */